SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Graph reduction</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Graph reduction</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about the computer science term. For the graph theory use, see <a href="Transitive_reduction" title="Transitive reduction">transitive reduction</a>.</div>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, <b>graph reduction</b> implements an efficient version of non-strict evaluation, an <a href="Evaluation_strategy" title="Evaluation strategy">evaluation strategy</a> where the arguments to a function are not immediately evaluated. This form of non-strict evaluation is also known as <a href="Lazy_evaluation" title="Lazy evaluation">lazy evaluation</a> and used in <a href="Functional_programming" title="Functional programming">functional programming languages</a>. The technique was first developed by Chris Wadsworth in 1971.

</p>

<div class="mw-heading mw-heading2"><h2 id="Motivation">Motivation</h2></div>

<p>A simple example of evaluating an arithmetic expression follows:

</p>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+(2+2))+6\\&{}&=&((2+2)+4)+6\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./ba837a13f9d802c8dbc3c56e2f7117da41a37cef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.671ex; width:35.619ex; height:18.509ex;" alt="{\displaystyle {\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+(2+2))+6\\&{}&=&((2+2)+4)+6\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>The above reduction sequence employs a strategy known as outermost tree reduction. The same expression can be evaluated using innermost tree reduction, yielding the reduction sequence:

</p>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+4)+(3+3)\\&{}&=&(4+4)+(3+3)\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./9683413b23ea4bdb7694d5ac53c6ade6bd2611d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.671ex; width:35.619ex; height:18.509ex;" alt="{\displaystyle {\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+4)+(3+3)\\&{}&=&(4+4)+(3+3)\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Notice that the reduction order is made explicit by the addition of parentheses. This expression could also have been simply evaluated right to left, because addition is an <a href="Associative" class="mw-redirect" title="Associative">associative</a> operation.

</p><p>Represented as a <a href="Tree_data_structure" class="mw-redirect" title="Tree data structure">tree</a>, the expression above looks like this:

</p><p><span typeof="mw:File"></span>

</p><p>This is where the term tree reduction comes from. When represented as a tree, we can think of innermost reduction as working from the bottom up, while outermost works from the top down.

</p><p>The expression can also be represented as a <a href="Directed_acyclic_graph" title="Directed acyclic graph">directed acyclic graph</a>, allowing sub-expressions to be shared:

</p><p><span typeof="mw:File"></span>

</p><p>As for trees, outermost and innermost reduction also applies to graphs. Hence we have <b>graph reduction</b>.

</p><p>Now evaluation with outermost graph reduction can proceed as follows:

</p><p><span typeof="mw:File"></span>

</p><p>Notice that evaluation now only requires four steps. Outermost graph reduction is referred to as <a href="Lazy_evaluation" title="Lazy evaluation">lazy evaluation</a> and innermost graph reduction is referred to as <a href="Eager_evaluation" class="mw-redirect" title="Eager evaluation">eager evaluation</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Combinator_graph_reduction">Combinator graph reduction</h2></div>

<p><b>Combinator graph reduction</b> is a fundamental implementation technique for <a href="Functional_programming" title="Functional programming">functional programming</a> languages, in which a program is converted into a <a href="Combinator" class="mw-redirect" title="Combinator">combinator</a> representation which is mapped to a <a href="Directed_graph" title="Directed graph">directed graph</a> <a href="Data_structure" title="Data structure">data structure</a> in computer memory, and program execution then consists of rewriting parts of this graph ("reducing" it) so as to move towards useful results.

</p>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<p>The concept of a graph reduction that allows evaluated values to be shared was first developed by Chris Wadsworth in his 1971 Ph.D. dissertation.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> This dissertation was cited by Peter Henderson and James H. Morris Jr. in 1976 paper, “A lazy evaluator”<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> that introduced the notion of lazy evaluation. In 1976 <a href="David_Turner_(computer_scientist)" title="David Turner (computer scientist)">David Turner</a> incorporated lazy evaluation into <a href="SASL_programming_language" class="mw-redirect" title="SASL programming language">SASL</a> using combinators.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

SASL was an early functional programming language first developed by Turner in 1972.

</p>

<ul><li><a href="Graph_reduction_machine" title="Graph reduction machine">Graph reduction machine</a></li>

<li><a href="SECD_machine" title="SECD machine">SECD machine</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFHudak1989" class="citation journal cs1"><a href="Paul_Hudak" title="Paul Hudak">Hudak, Paul</a> (September 1989). "Conception, evolution, and application of functional programming languages". <i>ACM Computing Surveys</i>. <b>21</b> (3): <span class="nowrap">359–</span>411. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.83.6505">10.1.1.83.6505</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F72551.72554">10.1145/72551.72554</a>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFHendersonMorris1976" class="citation conference cs1">Henderson, Peter; <a href="James_H._Morris" title="James H. Morris">Morris, James H.</a> (1976). <i>A lazy evaluator</i>. POPL '76: Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages. ACM Press. pp. <span class="nowrap">95–</span>103. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F800168.811543">10.1145/800168.811543</a>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFHudakHughesPeyton_JonesWadler" class="citation conference cs1"><a href="Paul_Hudak" title="Paul Hudak">Hudak, Paul</a>; <a href="John_Hughes_(computer_scientist)" title="John Hughes (computer scientist)">Hughes, John</a>; <a href="Simon_Peyton_Jones" title="Simon Peyton Jones">Peyton Jones, Simon</a>; <a href="Philip_Wadler" title="Philip Wadler">Wadler, Philip</a>. <a rel="nofollow" class="external text" href="http://haskell.org/haskellwiki/History_of_Haskell">"A History of Haskell: Being Lazy with Class"</a>. <i>History of Programming Languages Conference 2007</i>.</cite></span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFBird1998" class="citation book cs1">Bird, Richard (1998). <i>Introduction to Functional Programming using Haskell</i>. Prentice Hall. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-13-484346-0</bdi>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFPeyton_Jones1987" class="citation book cs1"><a href="Simon_Peyton_Jones" title="Simon Peyton Jones">Peyton Jones, Simon L.</a> (1987). <a rel="nofollow" class="external text" href="https://www.microsoft.com/en-us/research/publication/the-implementation-of-functional-programming-languages/"><i>The Implementation of Functional Programming Languages</i></a>. Prentice Hall. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>013453333X</bdi>. <a href="LCCN_(identifier)" class="mw-redirect" title="LCCN (identifier)">LCCN</a> <a rel="nofollow" class="external text" href="https://lccn.loc.gov/86020535">86020535</a><span class="reference-accessdate">. Retrieved <span class="nowrap">2022-04-15</span></span>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-22" href="https://en.wikipedia.org/wiki/?title=Graph_reduction&oldid=1286879071">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>